#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

//为什么空间优化要从左往右
//dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi)
//可以看到，dp[i][j]依赖的是当前位置的正上方和当前行的左方
//如果要用一行dp来表示，那么正上方的dp[i]就是自己，而左边的，需要通过从左往右更新来求得

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> items(n, vector<int>(2, 0));
    for (auto& item : items)
        cin >> item[0] >> item[1];

    vector<int> dp(v + 1, 0);
    for (int i = 1; i < n + 1; i++)
        for (int j = items[i - 1][0]; j < v + 1; j++)
            dp[j] = max(dp[j], dp[j - items[i - 1][0]] + items[i - 1][1]);

    cout << dp[v] << endl;

    //第二问
    //和01背包类似，如果没有选法可以使提及等于j，则dp[j] = -1; 
    dp = vector<int>(v + 1, -1);
    dp[0] = 0;
    for (int i = 1; i < n + 1; i++)
        for (int j = items[i - 1][0]; j < v + 1; j++)
            if (dp[j - items[i - 1][0]] != -1)
                dp[j] = max(dp[j], dp[j - items[i - 1][0]] + items[i - 1][1]);

    cout << (dp[v] == -1 ? 0 : dp[v]) << endl;

    return 0;
}


// dp[i][j]表示考虑前i个物品，体积小于等于j时的最大价值
// 和01背包同样的分析思路，dp[i][j]：
// dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vi] + wi, dp[i - 1][j - 2vi] + 2wi, dp[i - 1][j - 3vi] + 3wi, ....)
// 令j = j - vi
// dp[i][j - vi] = max(dp[i - 1][j - vi], dp[i - 1][j - 2vi] + wi, dp[i - 1][j - 3vi] + 2wi, dp[i - 1][j - 3vi] + 4wi, ....)
// 则可以得到：
// max(dp[i - 1][j - vi] + wi, dp[i - 1][j - 2vi] + 2wi, dp[i - 1][j - 3vi] + 3wi, ....) = 
// max(dp[i][j - vi] + wi)
// 即dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi)

// int main() {
//     int n, v;
//     cin >> n >> v;
//     vector<vector<int>> items(n, vector<int>(2, 0));
//     for (auto& item : items)
//         cin >> item[0] >> item[1];

//     vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
//     for (int i = 1; i < n + 1; i++)
//     {
//         for (int j = 1; j < v + 1; j++)
//         {
//             dp[i][j] = dp[i - 1][j];
//             if (j >= items[i - 1][0])
//                 dp[i][j] = max(dp[i][j], dp[i][j - items[i - 1][0]] + items[i - 1][1]);
//         }
//     }

//     cout << dp[n][v] << endl;

//     //第二问
//     //和01背包类似，如果没有选法可以使提及等于j，则dp[i][j] = -1; 
//     dp = vector<vector<int>>(n + 1, vector<int>(v + 1, 0));
//     for (int j = 1; j < v + 1; j++)
//         dp[0][j] = -1;
//     for (int i = 1; i < n + 1; i++)
//     {
//         for (int j = 1; j < v + 1; j++)
//         {
//             dp[i][j] = dp[i - 1][j];
//             if (j >= items[i - 1][0] && dp[i][j - items[i - 1][0]] != -1)
//                 dp[i][j] = max(dp[i][j], dp[i][j - items[i - 1][0]] + items[i - 1][1]);
//         }
//     }

//     cout << (dp[n][v] == -1 ? 0 : dp[n][v]) << endl;

//     return 0;
// }
// 64 位输出请用 printf("%lld")